TNotes.leetcode

Appearance

0230. 二叉搜索树中第 K 小的元素【中等】

0230. 二叉搜索树中第 K 小的元素【中等】 ​

1. 📝 题目描述 ​

给定一个二叉搜索树的根节点 root，和一个整数 k，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

示例 1：

img

txt
输入：root = [3, 1, 4, null, 2], k = 1
输出：1

示例 2：

img

txt
输入：root = [5, 3, 6, 2, 4, null, null, 1], k = 3
输出：3

提示：

  • 树中的节点数为 n。
  • 1 <= k <= n <= 10^4
  • 0 <= Node.val <= 10^4

进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

2. 🎯 s.1 - 中序遍历 ​

c
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int kthSmallest(struct TreeNode* root, int k) {
    struct TreeNode* stack[10000];
    int top = 0;
    struct TreeNode* node = root;
    while (node || top > 0) {
        while (node) {
            stack[top++] = node;
            node = node->left;
        }
        node = stack[--top];
        if (--k == 0)
            return node->val;
        node = node->right;
    }
    return -1;
}
js
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function (root, k) {
  const stack = []
  let node = root
  while (node || stack.length) {
    while (node) {
      stack.push(node)
      node = node.left
    }
    node = stack.pop()
    if (--k === 0) return node.val
    node = node.right
  }
}
py
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: Optional[TreeNode]
        :type k: int
        :rtype: int
        """
        stack = []
        node = root
        while node or stack:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            k -= 1
            if k == 0:
                return node.val
            node = node.right
  • 时间复杂度：O(H+k)，其中 H 是树的高度
  • 空间复杂度：O(H)，栈的大小

算法思路：

  • BST 的中序遍历产生升序序列
  • 用迭代式中序遍历，访问到第 k 个节点时立即返回

Discussions